The present invention relates to the field of sequencing methods and apparatus in data processing systems and particularly to microprogram control stores which provide improved performance.
Sequencing apparatus in data processing systems has been of various types, included "hard-wired" logic and microprogram control stores. In high-performance data processing systems, the sequencing apparatus frequently has been implemented as "hard-wired" logic circuitry capable of generating sequencing signals at high speeds. When flexibility has been required, the sequencing apparatus frequently has been implemented using microprogram control stores.
Microprogram control stores store many control words. Each control word represents many different bits of control information. Each control bit typically controls the state of some circuit within the data processing system.
Control words are stored at memory locations in control stores and the memory locations are defined by addresses. Each accessed control word establishes the control states within the data processing system. Each time a new control word is accessed, the control states are reestablished so that control states are changed from control word to control word, thereby controlling the sequence of operations of the data processing system. Accordingly, the repeated addressing and accessing of control words from memory locations in the control store determines the sequence of operation of the data processing system. Addresses of control words in a control store are frequently called microaddress. Control words are frequently called microinstructions. Groups of microinstructions, accessable in a predetermined sequence, are frequently called microprograms.
In order to access control words from a control store in a desired sequence, control store addresses are generated, one for each control word to be accessed. The generation of addresses in a predetermined sequence defined by a microprogram and the accessing of control words from the control store in that sequence determines the sequencing of units in a data processing system.
The control store addresses are provided in a predetermined order in accordance with a microprogram. In the absence of special conditions such as branches, the predetermined order of addresses in a microprogram typically consists of the sequential addresses that are designated by positive real integers (0, 1, 2, . . . , N). Such sequential addresses are typical provided by an address counter or other incrementer which increments the current address by one count to form the next-in-order sequential address each time the control store is to be addressed.
The desired predetermined sequence of control words constituting the microprogram of control words is stored in the control store memory at the predetermined sequential addresses.
In connection with sequencing operations, microprogram branching is normally provided. Among other things, branching reduces the required capacity of the control store, provides flexibility in microprogramming and permits data dependent operations to be performed. With branching, the sequence of control store addresses and therefore the sequence of accessing control words is altered from a next-in-order address to a branch address.
For example, where the next-in-order address is formed by adding one to the previous address, a branch occurs when the next address is formed in some manner other than by adding one to the previous address.
In data processing systems, branching can be of various types. One type is the unconditional branch which occurs when, at some predetermined microinstruction control word (called the "branch point of the sequencing), the sequencing always selects the branch address rather than the next-in-order (nonbranch) address. When the branch address is selected, the branch is said to be "taken" and when the next-in-order (nonbranch) address is selected, the branch is said to be "not taken." Another type of branching is the conditional branch. Under a conditional branch, the sequence of forming addresses and of accessing control words continues until the branch point is reached. At the branch point, a branch may be taken or may not be taken depending upon the state of some branch condition. If the branch condition is satisfied, then the sequencing continues with the branch address. If the branch condition is not satisifed, then the branch will not be taken and the nonbranch address will be selected.
The time at which the state of the branch condition becomes known determines the amount of delay, if any, which will be caused in the sequencing and execution of microinstructions. If the state of the branch condition is known prior to the time that the sequencing reaches the branch point, then no delay in the sequencing need occur. If the state of the branch condition has not been determined prior to the time that the sequencing reaches the branch point, then a delay in the sequencing may occur. Without special provisions, sequencing cannot continue past a branch point until the state of the branch condition has been determined.
Conditional branches may be two-way branches, three-way branches or multi-way branches of any number. In a two-way branch, at the branch point, the sequencing has a two-way choice. If the branch is not taken, the sequencing continues to the next-in-order nonbranch address. If the branch is taken, then the sequencing is to the branch address. In a three-way branch, if the branch is not taken, the sequencing is to the next-in-order nonbranch address. If the branch is taken, one of two branch addresses must be selected. In a three-way branch, the next-in-order address, the two branch addresses and the branch conditions for determining the three-way choice must be specified in some manner. Similarly, for multi-way branching, the multiple branch addresses and the multi-way branch conditions must all be specified.
When microprogram control stores are employed in high-speed data processing systems, a control word (microinstruction) is fetched typically in one cycle (called the "fetch" cycle) of the system and is executed (employed to control some operation) in the following cycle (called the execute cycle). Because of the relatively slow speed of control store memories in comparison with the short system cycle time, it is generally not possible in high-speed systems to both fetch a control word and to execute the same control word in the same system cycle. In a system where control words of a microprogram are accessed in one cycle and are executed in the following cycle, the presence of a branch point for a conditional branch will generally cause a one-cycle delay if the state of the branch condition is not known prior to the execute cycle which specifies a branch. Branch instructions frequently occur in microprograms and one-cycle or more delays are likely to occur when branch points are reached. Such delays substantially slow down the execution of microprograms and hence degrade the overall performance of data processing systems.
Accordingly, it is an objective of the present invention to provide sequencing apparatus and particularly microprogramming control store apparatus and methods which reduce or eliminate the delays resulting from branching in the microprogram.